Math 419/592 Homework for Chapter 4 For any problem that involves finding numerical steady-state values, do _not_ do it by hand; instead, use Excel, Matlab, or some other similar tool. If the problem involves symbolic steady-state values, then you may do it by hand. None of these questions use any randomness like =RAND(). These problems refer to the 8th edition, but you can use the hints to figure out which problems they became in the 10th edition. ---------------------------------------------------------------------- Problem 4.29 Employee job classifications (this is pretty easy) [4pts] ---------------------------------------------------------------------- Economic Quintile Problem Use the graph at http://mapleta.emich.edu/aross15/coursepack3419/opportunity-1.png to create a Markov Chain model of income mobility from one generation to the next. The 1st quintile is the poorest, and the 5th is the richest. a) What is the transition matrix? Figure out where each number goes. There is a subtle issue here--what is it? Figure out what it is and fix it. b) If you are in the 5th quintile, what is the probability that your grandson will be in the 1st quintile? c) What is the steady-state distribution? Compute it using methods learned in class. d) Explain the result you got in part (c). e) Suppose you are a bleeding-heart liberal. What would you want the transition matrix in part (a) to look like? f) Suppose you are a conservative with a heart of stone. What would you want the transition matrix in part (a) to look like? ---------------------------------------------------------------------- Problem 4.33 Three types of exams (also not too bad) [4 pts for matrix, 4 for solution] ---------------------------------------------------------------------- Problem 4.46 Hints: Does it work if your state is "# of umbrellas at home"? What about "# of umbrellas at work"? Any other ideas? Ultimately, your transition matrix will have a diagonal look to it, but from lower-left to upper-right as opposed to the usual matrix diagonal. Once you have the matrix, finding the steady-state solution is pretty much guess-and-check, and they give you the guess. You should formally check it, though. [4 for matrix, 4 for pi proof, 4 for Pr(wet), 4 for maximizing] ---------------------------------------------------------------------- Problem 4.52. It's possible to do this using a 2-state or a 4-state chain; I recommend the 2-state. First, find the proportion of trips that start in zone A. Then, find the expected profit per trip starting in zone A. Then, the expected profit per trip starting in zone B. Then, combine them for the overall expected profit per trip. Hint: one of the intermediate values you might get in this problem is 0.4285714 [4 for matrix, 4 for pi vector, 4 for average cost] ---------------------------------------------------------------------- An inventory problem. Suppose we receive a shipment of 3 items every day. Our daily demand has a Uniform distribution on 0,1,2,3,4,5,6,7, with no changes in behavior according to day-of-the-week. Our warehouse only has room for 10 items during the overnight period. Here is the timeline for events: Midnight: take inventory; this is the DTMC state variable 6am: receive shipment of 3 items. 8am-9pm: demand occurs. If we run out of inventory, orders are lost (as opposed to being backordered) 10pm: discard excess inventory that won't fit in the warehouse. Midnight: take inventory again, etc. Questions: (a) Formulate the transition matrix. Hint: the value in the upper- left corner is 0.625 (b) What is the probability we end up with nothing in the warehouse overnight? Hint: it's around 0.3 (c) If it costs $10 per item in the warehouse overnight, what is our average inventory cost per night? Hint: it's around $28 or $29 The following part is for grad students, though of course undergrads should contemplate it. The calculations are somewhat intricate. (d) What is the average number of items discarded per night due to warehouse limitations? Also, for everyone to contemplate but not solve unless you really want to: (e) What fraction of our customers find us out of stock? [4 for each part] ---------------------------------------------------------------------- For the highway repair problem discussed in class, suppose you follow the policy beta= E M C N G [ 0 0 .4 .6 ] F [ 0 0 1 0 ] B [ .1 .2 .7 0 ] Define X0 to be the status in the year 2007, and X1 to be the status in the year 2008. What is Pr(X1 = G | X0 = B)? (I might have said Poor instead of Bad; they mean the same thing) [4 pts] ---------------------------------------------------------------------- Read and contemplate problems 4.41 and 4.42, about the balance equations pi=pi*P. Write in your homework your questions about the problem statements. Comment on your level of understanding. [4 pts] ---------------------------------------------------------------------- This problem is optional for 2011, but mandatory in future years. This problem is inspired by a question from "Finite Markov Chains and Algorithmic Applications" by Olle Haggstrom. Consider a simple set of web pages: A links to B and C B links to A and D C links to A D links to A, B, and C a) Write down the DTMC matrix for a random web surfer who picks an outbound link with equal probability from all outbound links on the current page. b) Now suppose that in addition to following links, the surfer might randomly jump to any page on this little web (including the current page) by doing a search. This happens with probability 0.15. Can you still describe this situation with a Markov Chain? Explain. If so, what does the new transition matrix look like? c) Now ignore the modification in part (b) and consider the model from part (a) again. Suppose that the random surfer hits the "back" button on the browser with probability 0.05. Can you still describe this situation with a Markov Chain? Explain. If so, what does the new transition matrix look like? [4 pts for each part] ---------------------------------------------------------------------- This problem is optional for 2011, but mandatory in future years. This problem is inspired by a question from "Finite Markov Chains and Algorithmic Applications" by Olle Haggstrom. Consider a DTMC whose states are labelled "-1", "0", and "+1", and whose transition matrix is: to: -1 0 +1 from -1: [ 0 1 0 ] from 0: [ 0 0 1 ] from +1: [ 1 0 0 ] a) Suppose you generate data from this DTMC for 10 steps, starting with -1. What would that data look like? X_0 = -1 X_1 = ? X_2 = ? etc. b) Let f(x) = x^2, and let Y_n = f(X_n); that is, Y_n is a function of the data from the original DTMC. Generate data for the first 10 steps of Y_n: Y_0 = (-1)^2 = +1 Y_1 = ? Y_2 = ? etc. c) Is Y_n a Markov Chain? Explain. If so, give the transition matrix. [4 pts] ---------------------------------------------------------------------- for grad students (though undergrads should also read these and contemplate): Choose one of these three problems. Each is worth 16 total points. Problem 4.36: A Hidden Markov Model Do the problem as specified in the book. Then, do the following extension: Prof. Ross has generated data on Y using P=[.04 .96; .96 .04], and p0 = .02, p1 = .97 and put it on the web: http://people.emich.edu/aross15/math419/4_36data.txt Take this Y data and show that Pr{Y_{n}=1 | Y_{n-1}=1} is different than Pr{Y_{n}=1 | Y_{n-1}=1 and Y_{n-2}=1}; and that's different than using 3 steps of history, etc. This shows that the Yn values are not a Markov chain. Three Independent Machines: Consider a system with three independent machines. Each one has a probability "f" of failing on any particular day that it's working, and then once it's broken it has a probability "r" of being repaired on any particular day. a) Formulate a DTMC that describes this system of 3 machines. Your formulation could have 4 states or 8 states; I recommend 8 states, because it's easier to figure out the transition probabilities. b) Guess a symbolic steady-state distribution and check that it is true. Gambler's Ruin with Ties Let's modify Gambler's Ruin to allow a coin-flip to result in a tie. Now, Pr{lose once}=a, Pr{tie}=b, Pr{win once}=c, with a+b+c=1. a) Write down a new system of linear equations that the P_i values must satisfy. b) Guess a new formula to solve the new set of linear equations. Recall that the solution to the linear equations without ties was P_i = (1-gamma^i)/(1-gamma^N), where gamma=q/p (I may have used the name alpha in class instead of gamma; whatever.) Hint: does it work to just change the definition of gamma? You may ignore the case where we might divide by zero. Show that your guess indeed solves the system of linear equations. c) What is the new system of equations for M_i ?